home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / TEMP / GNU / bison / Glossary < prev    next >
Text File  |  1995-06-28  |  7KB  |  219 lines
  1. Glossary
  2. Previous: <Table of Symbols=>TableofSym> * Next: <Index=>Index> * Up: <Top=>!Root>
  3.  
  4. #Wrap on
  5. {fH2}Glossary{f}
  6.  
  7. #Indent +4
  8. #Indent
  9. Backus-Naur Form (BNF)
  10. #Indent +4
  11. Formal method of specifying context-free grammars.  BNF was first used
  12. in the {fCite}ALGOL-60{f} report, 1963.  \*Note <Language and Grammar=>Languagean>: Languages and Context-Free Grammars.
  13.  
  14. #Indent
  15. Context-free grammars
  16. #Indent +4
  17. Grammars specified as rules that can be applied regardless of context.
  18. Thus, if there is a rule which says that an integer can be used as an
  19. expression, integers are allowed {fEmphasis}anywhere{f} an expression is
  20. permitted.  \*Note <Language and Grammar=>Languagean>: Languages and Context-Free Grammars.
  21.  
  22. #Indent
  23. Dynamic allocation
  24. #Indent +4
  25. Allocation of memory that occurs during execution, rather than at
  26. compile time or on entry to a function.
  27.  
  28. #Indent
  29. Empty string
  30. #Indent +4
  31. Analogous to the empty set in set theory, the empty string is a
  32. character string of length zero.
  33.  
  34. #Indent
  35. Finite-state stack machine
  36. #Indent +4
  37. A ``machine'' that has discrete states in which it is said to exist at
  38. each instant in time.  As input to the machine is processed, the
  39. machine moves from state to state as specified by the logic of the
  40. machine.  In the case of the parser, the input is the language being
  41. parsed, and the states correspond to various stages in the grammar
  42. rules.  \*Note <Algorithm=>Algorithm>: The Bison Parser Algorithm .
  43.  
  44. #Indent
  45. Grouping
  46. #Indent +4
  47. A language construct that is (in general) grammatically divisible;
  48. for example, `expression' or `declaration' in C.  
  49. \*Note <Language and Grammar=>Languagean>: Languages and Context-Free Grammars.
  50.  
  51. #Indent
  52. Infix operator
  53. #Indent +4
  54. An arithmetic operator that is placed between the operands on which it
  55. performs some operation.
  56.  
  57. #Indent
  58. Input stream
  59. #Indent +4
  60. A continuous flow of data between devices or programs.
  61.  
  62. #Indent
  63. Language construct
  64. #Indent +4
  65. One of the typical usage schemas of the language.  For example, one of
  66. the constructs of the C language is the {fCode}if{f} statement.
  67. \*Note <Language and Grammar=>Languagean>: Languages and Context-Free Grammars.
  68.  
  69. #Indent
  70. Left associativity
  71. #Indent +4
  72. Operators having left associativity are analyzed from left to right:
  73. {fEmphasis}a+b+c{f} first computes {fEmphasis}a+b{f} and then combines with
  74. {fEmphasis}c{f}.  \*Note <Precedence=>Precedencf>: Operator Precedence.
  75.  
  76. #Indent
  77. Left recursion
  78. #Indent +4
  79. A rule whose result symbol is also its first component symbol;
  80. for example, {fEmphasis}expseq1 : expseq1 ',' exp;{f}.  \*Note <Recursion=>Recursion>: Recursive Rules.
  81.  
  82. #Indent
  83. Left-to-right parsing
  84. #Indent +4
  85. Parsing a sentence of a language by analyzing it token by token from
  86. left to right.  \*Note <Algorithm=>Algorithm>: The Bison Parser Algorithm .
  87.  
  88. #Indent
  89. Lexical analyzer (scanner)
  90. #Indent +4
  91. A function that reads an input stream and returns tokens one by one.
  92. \*Note <Lexical=>Lexical>: The Lexical Analyzer Function {fCode}yylex{f}.
  93.  
  94. #Indent
  95. Lexical tie-in
  96. #Indent +4
  97. A flag, set by actions in the grammar rules, which alters the way
  98. tokens are parsed.  \*Note <Lexical Tie-ins=>LexicalTie>.
  99.  
  100. #Indent
  101. Look-ahead token
  102. #Indent +4
  103. A token already read but not yet shifted.  \*Note <Look-Ahead=>LookAhead>: Look-Ahead Tokens.
  104.  
  105. #Indent
  106. LALR(1)
  107. #Indent +4
  108. The class of context-free grammars that Bison (like most other parser
  109. generators) can handle; a subset of LR(1).  \*Note <Mystery Conflicts=>MysteryCon>: Mysterious Reduce\/Reduce Conflicts.
  110.  
  111. #Indent
  112. LR(1)
  113. #Indent +4
  114. The class of context-free grammars in which at most one token of
  115. look-ahead is needed to disambiguate the parsing of any piece of input.
  116.  
  117. #Indent
  118. Nonterminal symbol
  119. #Indent +4
  120. A grammar symbol standing for a grammatical construct that can
  121. be expressed through rules in terms of smaller constructs; in other
  122. words, a construct that is not a token.  \*Note <Symbols=>Symbols>.
  123.  
  124. #Indent
  125. Parse error
  126. #Indent +4
  127. An error encountered during parsing of an input stream due to invalid
  128. syntax.  \*Note <Error Recovery=>ErrorRecov>.
  129.  
  130. #Indent
  131. Parser
  132. #Indent +4
  133. A function that recognizes valid sentences of a language by analyzing
  134. the syntax structure of a set of tokens passed to it from a lexical
  135. analyzer.
  136.  
  137. #Indent
  138. Postfix operator
  139. #Indent +4
  140. An arithmetic operator that is placed after the operands upon which it
  141. performs some operation.
  142.  
  143. #Indent
  144. Reduction
  145. #Indent +4
  146. Replacing a string of nonterminals and\/or terminals with a single
  147. nonterminal, according to a grammar rule.  \*Note <Algorithm=>Algorithm>: The Bison Parser Algorithm .
  148.  
  149. #Indent
  150. Reentrant
  151. #Indent +4
  152. A reentrant subprogram is a subprogram which can be in invoked any
  153. number of times in parallel, without interference between the various
  154. invocations.  \*Note <Pure Decl=>PureDecl>: A Pure (Reentrant) Parser.
  155.  
  156. #Indent
  157. Reverse polish notation
  158. #Indent +4
  159. A language in which all operators are postfix operators.
  160.  
  161. #Indent
  162. Right recursion
  163. #Indent +4
  164. A rule whose result symbol is also its last component symbol;
  165. for example, {fEmphasis}expseq1: exp ',' expseq1;{f}.  \*Note <Recursion=>Recursion>: Recursive Rules.
  166.  
  167. #Indent
  168. Semantics
  169. #Indent +4
  170. In computer languages, the semantics are specified by the actions
  171. taken for each instance of the language, i.e., the meaning of
  172. each statement.  \*Note <Semantics=>Semantics>: Defining Language Semantics.
  173.  
  174. #Indent
  175. Shift
  176. #Indent +4
  177. A parser is said to shift when it makes the choice of analyzing
  178. further input from the stream rather than reducing immediately some
  179. already-recognized rule.  \*Note <Algorithm=>Algorithm>: The Bison Parser Algorithm .
  180.  
  181. #Indent
  182. Single-character literal
  183. #Indent +4
  184. A single character that is recognized and interpreted as is.
  185. \*Note <Grammar in Bison=>GrammarinB>: From Formal Rules to Bison Input.
  186.  
  187. #Indent
  188. Start symbol
  189. #Indent +4
  190. The nonterminal symbol that stands for a complete valid utterance in
  191. the language being parsed.  The start symbol is usually listed as the
  192. first nonterminal symbol in a language specification.  
  193. \*Note <Start Decl=>StartDecl>: The Start-Symbol.
  194.  
  195. #Indent
  196. Symbol table
  197. #Indent +4
  198. A data structure where symbol names and associated data are stored
  199. during parsing to allow for recognition and use of existing
  200. information in repeated uses of a symbol.  \*Note <Multi-function Calc=>Multifunct>.
  201.  
  202. #Indent
  203. Token
  204. #Indent +4
  205. A basic, grammatically indivisible unit of a language.  The symbol
  206. that describes a token in the grammar is a terminal symbol.
  207. The input of the Bison parser is a stream of tokens which comes from
  208. the lexical analyzer.  \*Note <Symbols=>Symbols>.
  209.  
  210. #Indent
  211. Terminal symbol
  212. #Indent +4
  213. A grammar symbol that has no rules in the grammar and therefore
  214. is grammatically indivisible.  The piece of text it represents
  215. is a token.  \*Note <Language and Grammar=>Languagean>: Languages and Context-Free Grammars.
  216.  
  217. #Indent
  218.  
  219.